package leetcode

func trailingZeroes(n int) int {
	// 使用从编程之美中看到的解法：质因数分解，最终转换为n的质因数中有多少个5
	// 最简单的解法是遍历1到n，分别计算他们的质因数5的个数，然后加起来，但这样是o(n*log5n)，效率不行
	// 编程之美中提出，可以考虑从1到n中分别包含5,5^2,..5^k次的倍数的个数，每个倍数分别在每次看5^i的倍数时提供一次5
	// 而1-n中5^k的倍数个数，可以直接用[n/5^k]得到，故而有以下算法
	cnt := 0
	for n != 0 {
		cnt += n / 5
		n = n / 5
	}
	return cnt
}
